翻訳と辞書 Words near each other ・ Christoffer Selbekk ・ Christoffer Sundby ・ Christoffer Sundgren ・ Christoffer Sundqvist ・ Christoffer Svae ・ Christoffer Törngren ・ Christoffer Urne ・ Christoffer Valkendorff ・ Christoffer Vikström ・ Christoffer Wiktorsson ・ Christoffer Wilhelm Eckersberg ・ Christoffer Østergaard ・ Christoffersen ・ Christoffersen Heights ・ Christoffersen Island ・ Christofides algorithm ・ Christofilos effect ・ Christofle ・ Christoforo Borri ・ Christoforos Bakaoukas ・ Christoforos Charalambous ・ Christoforos Knitis ・ Christoforos Kourtis ・ Christoforos Liontakis ・ Christoforos Loizou ・ Christoforos Nezer ・ Christoforos Nezer (Bavarian) ・ Christoforos Nezer (d. 1970) ・ Christoforos Nezer (d. 1996) ・ Christoforos Papakaliatis Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Christofides algorithm ： ウィキペディア英語版 Christofides algorithm The goal of the Christofides approximation algorithm (named after Nicos Christofides) is to find a solution to the instances of the traveling salesman problem where the edge weights satisfy the triangle inequality. Let $G=(V,w)$ be an instance of TSP, i.e. $G$ is a complete graph on the set $V$ of vertices with weight function $w$ assigning a nonnegative real weight to every edge of $G$. == Algorithm == In pseudo-code: # Create a minimum spanning tree $T$ of $G$. # Let $O$ be the set of vertices with odd degree in $T$ and find a perfect matching $M$ with minimum weight in the complete graph over the vertices from $O$. # Combine the edges of $M$ and $T$ to form a multigraph $H$. # Form an Eulerian circuit in $H$ (H is Eulerian because it is connected, with only even-degree vertices). # Make the circuit found in previous step Hamiltonian by skipping visited nodes (''shortcutting''). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Christofides algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.